package fun.coding.tree.bst;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;

public class BinarySearchTreeImpl implements BinarySearchTree {
	
	@Override
	public void insert(BSTNode node, int value) {
	    // This is to check if the tree head is null or not.
		if(node == null) {
			node = new BSTNode();
			node.setValue(value);
			node.setLeft(null);
			node.setRight(null);
			System.out.println(String.format("inserted head %d", value));
			return;
		}
		
		if(value < node.getValue()) {
		    if(node.getLeft() == null) {
		        node.setLeft(new BSTNode(value));
		        System.out.println(String.format("inserted left %d", value));
		        return;
		    }
		    insert(node.getLeft(), value);
		} else if(value > node.getValue()) {
		    if(node.getRight() == null) {
		        node.setRight(new BSTNode(value));
		        System.out.println(String.format("inserted right %d", value));
		        return;
		    }
			insert(node.getRight(), value);
		} else {
			// I assume there is no duplicate in this tree.
			return;
		}
		
	}

	/* delete is slighly more complicated to implement. 
	 * (non-Javadoc)
	 * @see interview.coding.tree.bst.BinarySearchTree#delete(int)
	 */
	@Override
	public void delete(int value) {
		
	}

	/* Let's assume there is no duplicate in this bst.
	 * (non-Javadoc)
	 * @see interview.coding.tree.bst.BinarySearchTree#find(interview.coding.tree.bst.BSTNode, int)
	 * @return will return -1 if there is no such element. 
	 */
	@Override
	public int find(BSTNode node, int value) {
	    if(node == null) {
	        return -1;
	    }
	    
	    if(value < node.getValue()) {
	        return find(node.getLeft(), value);
	    } else if(value > node.getValue()) {
	        return find(node.getRight(), value);
	    } else {
            return value;
	    }
	}

    @Override
    public void inOrderTraversal(BSTNode node) {
        if(node == null) {
            return;
        }
        /*
        inOrderTraversal(node.getLeft());
        System.out.println(node.getValue());
        inOrderTraversal(node.getRight());
        */
        // This will give the reverse in order
        inOrderTraversal(node.getRight());
        System.out.println(node.getValue());
        inOrderTraversal(node.getLeft());
    }
    
    @Override 
    public ArrayList<Integer> inOrderTraversalArray(BSTNode node) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        inOrderTraversalArrayHelper(node, res);
        return res;
    }
    
    private void inOrderTraversalArrayHelper(BSTNode node, ArrayList<Integer> res) {
        if(node == null) 
            return;
        inOrderTraversalArrayHelper(node.getLeft(), res);
        res.add(node.getValue());
        inOrderTraversalArrayHelper(node.getRight(), res);
    }
    
    
    @Override
    public void preOrderTraversal(BSTNode node) {
        if(node == null) {
            return;
        }
        System.out.println(node.getValue());
        preOrderTraversal(node.getLeft());
        preOrderTraversal(node.getRight());
    }

    @Override
    public void postOrderTraversal(BSTNode node) {
        // TODO Auto-generated method stub
        
    }

    private int count = 0; // count for how many nodes have been counted in find kth largest element.
    /* Need to keep a global counter for the count.
     * traverse the tree through the left node first if finding kth smallest.
     * */
    @Override
    public void findKthLargestNode(BSTNode head, int k) {
        if(head == null) {
            return;
        }
        
        if(count < k) {
            findKthLargestNode(head.getRight(), k);
            count++;
        }
        
        if(count == k) {
            System.out.println("The " + k +"th largest element is " + head.getValue());
            return;
        }
        // only need to increase the counter for one end. 
        if(count < k) {
            findKthLargestNode(head.getLeft(), k);
        }
        
        return;
    }

    @Override
    public boolean isIsomorphic(BSTNode head1, BSTNode head2) {
        // FIXME: this doesn't really work for my binary tree case... 
        if(head1 == null && head2 == null) {
            return true;
        }
        
        if((head1 == null && head2 != null) || (head1 != null && head2 == null)) {
            return false;
        }
        
        return isIsomorphic(head1.getLeft(), head2.getRight()) && isIsomorphic(head1.getRight(), head2.getLeft());

    }

    /*
     * Let's assume going left is 0, and going right is 1. 
     */
	@Override
	public void printOutHuffmanCoding(BSTNode head, int k) {
		if(head == null) {
			return;
		}
		
		if(k < head.getValue()) {
			System.out.print("0");
			printOutHuffmanCoding(head.getLeft(), k);
		} else if(k > head.getValue()) {
			System.out.print("1");
			printOutHuffmanCoding(head.getRight(), k);
		} else {
			return;
		}
	}

	/*
	 * print out a tree in each level
	 * 
	 * 1) revised this by putting a '\n' in each level, whenever poping out '\n', a new '\n' would be inserted. 
	 * 2) keep track of two queues, and keep switching them when one queue is empty and print out a space
	 * 3) keep a current of current level and next level. 
	 */
	public Queue<BSTNode> q = new LinkedList<BSTNode>();
	@Override
	public void levelOrderTraversal(BSTNode node) {
		if(node == null) {
			return;
		}
        System.out.println("\nlevel order traversal is ");
		q.add(node);
		int nodeInCurrentLevel = 1;
		int nodeInNextLevel = 0;
		
		while(!q.isEmpty()) {
			
			BSTNode curNode = q.poll();
			System.out.print(curNode.getValue() + ",");
			nodeInCurrentLevel--;
			
			if(curNode.getLeft() != null) {
				q.offer(curNode.getLeft());
				nodeInNextLevel += 1;
			}
			
			if(curNode.getRight() != null) {
				q.offer(curNode.getRight());
				nodeInNextLevel += 1;
			}
			
			if(nodeInCurrentLevel == 0) {
				System.out.println();
				nodeInCurrentLevel = nodeInNextLevel;
				nodeInNextLevel = 0;
			}
		}
	
	}
	
	/* This is method 2, using 2 queues to finish this
	 * This could be applied to making the tree into D depth list*/
	@Override
    public void levelOrderTraversalList(BSTNode node) {
	    if(node == null)
	        return;
	    
	    LinkedList<BSTNode> parent = new LinkedList<BSTNode>();
	    parent.add(node);
	    
	    while(!parent.isEmpty()) {
	        LinkedList<BSTNode> current = new LinkedList<BSTNode>();
	        for(BSTNode n : parent) {
	            if(n.getLeft() != null)
	                current.add(n.getLeft());
	            if(n.getRight() != null)
	                current.add(n.getRight());
	            System.out.print(n.getValue() + " ");
	        }
	        System.out.println();
	        parent = current;
	    }
    }

	/* Microsoft online judge question, level 0 means root. 
	 * */
	@Override
	public void levelOrderPrintOneLevel(BSTNode node, int level) {
		if(node == null)
	        return;
	    
		int currentLevel = 0;
	    LinkedList<BSTNode> parent = new LinkedList<BSTNode>();
	    parent.add(node);
	    
	    while(!parent.isEmpty()) {
	        LinkedList<BSTNode> current = new LinkedList<BSTNode>();
	        for(BSTNode n : parent) {
	            if(n.getLeft() != null)
	                current.add(n.getLeft());
	            if(n.getRight() != null)
	                current.add(n.getRight());
	        }
	        if(currentLevel == level) {
	        	for(BSTNode n : parent) {
	        		System.out.print(n.getValue() + " ");
	        	}
	        	break;
	        }
	        currentLevel++;
	        parent = current;
	    }
		
	}
	
	
	public Queue getQ() {
		return q;
	}

	/*
	 * Return the height of a binary tree.
	 * @see interview.coding.tree.bst.BinarySearchTree#getTreeHeight(interview.coding.tree.bst.BSTNode)
	 */
	@Override
	public int getTreeHeight(BSTNode head) {
		
		if(head == null) {
			return 0;
		}
		
		return Math.max(getTreeHeight(head.getLeft()), getTreeHeight(head.getRight())) + 1;
	}

	/*
	 * Using pre-order to flatten a binary tree
	 *   1
        / \
       2   5
      / \   \
     3   4   6
      \
       9
        \
         7
   1
    \
     2
      \
       3
        \
         9
          \
           7
            \
             4
              \
               5
                \
                 6
                 It is not hard at all...
	 */
	@Override
	public void flatten(BSTNode head) {
		if(head == null) {
			return;
		}
		
		if(head.getLeft() != null) {
			flatten(head.getLeft());
			
			BSTNode curr = head.getLeft();
			
			// need to find the right most child.
			while(curr.getRight() != null) {
				curr = curr.getRight();
			}
			
			// swap the node
			curr.setRight(head.getRight());
			head.setRight(head.getLeft());
			head.setLeft(null);
		}
		
		flatten(head.getRight());
	}

	@Override
	public boolean isBalanced(BSTNode head) {
		if(head == null) {
			return true;
		}
		
		int diff = Math.abs(getTreeHeight(head.getLeft()) - getTreeHeight(head.getRight()));
		
		if(diff > 1)
			return false;
		
		return  isBalanced(head.getLeft()) && isBalanced(head.getRight());
	}

	/*
	 * Determine if a tree is a BST by printing out the in-order
	 * Note: using too much extra space, not good for interviews. 
	 */
    @Override
    public boolean isBST(BSTNode head) {
        
        ArrayList<Integer> al = new ArrayList<Integer>();
        inOrder(al, head);
        return isAscending(al);
        /*
        for(int i : al) {
            System.out.println(i);
        }
        */
        
    }
    
    /* netflix onsite. failed on this one
     * */
    @Override
    public boolean isBSTBetter(BSTNode head, int max, int min) {
        if(head == null)
            return true;
        
        if(head.getValue() > max || head.getValue() < min) {
            return false;
        } else {
            return isBSTBetter(head.getLeft(), head.getValue(), min) && isBSTBetter(head.getRight(), max, head.getValue()); 
        }
        
    }
    
    /* Just directly used an in order traversal since we only need to compare the current value with the previous one. 
     * Thereore, we don't really need to store the values in an array. 
     * */
    private int lastVisitedValue = Integer.MIN_VALUE;
    @Override
    public boolean isBSTInorder(BSTNode head) {
        if(head == null)
            return true;
        
        if(!isBSTInorder(head.getLeft()))
            return false;
        if(head.getValue() < lastVisitedValue)
            return false;
        else 
            lastVisitedValue = head.getValue();
        
        if(!isBSTInorder(head.getRight()))
            return false;
        return true;
    }
    
    
    
    private void inOrder(ArrayList<Integer> al, BSTNode head) {
        if(head == null)
            return;
        
        inOrder(al, head.getLeft());
        al.add(head.getValue());
        inOrder(al, head.getRight());
    }

    private boolean isAscending(ArrayList<Integer> al) {
        
        for(int i = 0; i < al.size() - 1; ++i) {
            if(al.get(i) > al.get(i+1))
                return false;
        }
        return true;
    }

    /*
     * This will work for any binary tree, not just BST
     * Recursivly build up the tree. The idea is to divide the tree using preorder, thus
     * partition the inorder into left and right two parts, keeping both the inorder and preorder index, 
     * using the length to know how many elements are in the subtree.  
     * 
     * The look up element can be optimized by using a hashmap, but need to keep track of an extra offset. 
     *   int[] inOrder = {4, 10, 3, 1, 7, 11, 8, 2};
        int[] preOrder = {7, 10, 4, 3, 1, 2, 8, 11};
        
         _____7______
       /              \
    __10__          ___2
   /      \        /
   4       3      _8
            \    /
             1  11
     *   
     *   
     *   C++
     *   http://www.leetcode.com/2011/04/construct-binary-tree-from-inorder-and-preorder-postorder-traversal.html
     *   Java version:
     *   http://crackinterviewtoday.wordpress.com/2010/03/15/rebuild-a-binary-tree-from-inorder-and-preorder-traversals/
     */
    @Override
    public BSTNode buildBinaryTreeFromInOrderPreOrder(int[] inOrder,
            int[] preOrder, int inOrderIndex, int preOrderIndex, int length) {
        if(length == 0)
            return null;
        
        int rootIndex = 0; 
        
        for(int i = inOrderIndex; i < inOrder.length; ++i) {
            if(inOrder[i] == preOrder[preOrderIndex]) {
                break;
            }
            
            rootIndex++;
        }
                
        BSTNode root = new BSTNode(preOrder[preOrderIndex]);
        
        root.setLeft(buildBinaryTreeFromInOrderPreOrder(inOrder, preOrder, inOrderIndex, preOrderIndex + 1, rootIndex));
        root.setRight(buildBinaryTreeFromInOrderPreOrder(inOrder, preOrder, inOrderIndex + rootIndex + 1, preOrderIndex + rootIndex + 1, length - rootIndex - 1));
        
        return root;
    }

    @Override
    public BSTNode cloneBST(BSTNode head) {
        //TODO:	
        return null;
    }

    @Override
    public BSTNode mirrorBST(BSTNode head) {
        // TODO Auto-generated method stub
        return null;
    }

    /* Count how many nodes are there in a binary tree.
     * 
     * */
    @Override
    public int countBSTNode(BSTNode head) {
        if(head == null)
            return 0;
        
        return 1 + countBSTNode(head.getLeft()) + countBSTNode(head.getRight());
    }

    /*
     * 
     */
    @Override
    public int countBSTLeaf(BSTNode head) {
        if(head == null)
        	return 0;
    	
        if(head.getLeft() == null && head.getRight() == null) {
        	return 1;
        }
        
        return countBSTLeaf(head.getLeft()) + countBSTLeaf(head.getRight());
    }

    /* 
     *    1
     *   / \
     *  2   3
     * / \  /\
     *6   9 8  1
     *   return 9+2+1+3+8
     *   
     *   there could be negative values in the tree
     *       1
     *    -2  3
     *      return 1+3
     *      
     *      http://blog.csdn.net/zhiyu27/article/details/8186372
     *      
     * */
    private int max;
    @Override
    public int maxPathSum(BSTNode head) {
        return Math.max(maxPathSumHelper(head), max);   
    }
    
    private int maxPathSumHelper(BSTNode head) {
        if(head == null)
            return 0;
        
        int leftMax = maxPathSumHelper(head.getLeft());
        int rightMax = maxPathSumHelper(head.getRight());
        
        int localMax = head.getValue();
        
        if(leftMax > 0)
            localMax += leftMax;
        
        if(rightMax > 0) 
            localMax += rightMax;
        
        // This max records the global max
        max = Math.max(localMax, max);
        
        // This return the current max sum path, it can only be either the current node, it is left + itself or right + itself
        return Math.max(head.getValue(), Math.max(head.getValue() +leftMax, head.getValue() + rightMax));
        
    }


    
    
    

	
}
